//
// Created by 麻再挺 on 2021/12/20.
//

#include "btree.h"

/**
 * 在结点 p 中查找关键字 key 的插入位置 i
 * @param p 结点
 * @param key 关键字
 * @return 插入位置
 */
int Search_BTNode(BTNode *p, BKeyType key) {
    int i;
    // 小于结点数, 并且值小于等于关键字
    for (i = 0; i < p->keyNum && p->key[i + 1] <= key; ++i);
    return i;
}

/**
 * 在树中查找关键字
 * @param t 树
 * @param key 关键字
 * @return 结果
 */
BResult Search_BTree(BTree t, BKeyType key) {
    // 初始化结点 p 和结点 q, p 指向待查结点, q 指向 p 的双亲
    BTNode *p = t, *q = NULL;
    // 设定查找成功与否标志
    int tag = 0;
    // 设置返回的查找结果
    BResult res;
    int i = 0;
    // 循环查找
    while (p != NULL && tag == 0) {
        // 在结点 p 中查找关键字 key
        i = Search_BTNode(p, key);
        // 位置大于 0 并且关键字相等, 说明已经查找到
        if (i > 0 && p->key[i] == key) {
            tag = 1;
        } else {
            // 进入此处说明未找到
            // 保存双亲
            q = p;
            // 向下查找
            p = p->ptr[i];
        }
    }

    if (tag == 1) {
        // 查找成功
        res.tag = true;
        res.i = i;
        res.pt = p;
    } else {
        // 查找失败
        res.tag = false;
        res.i = i;
        res.pt = q;
    }

    return res;
}

/**
 * 初始化队列
 * @param list 列表
 */
Status Init_BTree_Queue(BLinkedList *list) {
    *list = (BLNode *) malloc(sizeof(BLNode));
    if (list == NULL) return OVERFLOW;
    (*list)->next = NULL;
    return OK;
}

/**
 * 创建队列结点
 * @param q 树结点
 * @return 队列结点
 */
BLNode *CreateBtreeNode(BTNode *p) {
    BLNode *q;
    // 分配结点空间
    q = malloc(sizeof(BLNode));
    if (q != NULL) {
        q->data = p;
        q->next = NULL;
    }
    return q;
}

/**
 * 入队
 * @param p 对结点
 * @param q 树结点
 * @return
 */
Status BTree_EnQueue(BLNode *p, BTNode *q) {
    if (p == NULL) return ERROR;
    // 移动至队列的最后
    while (p->next != NULL) p = p->next;
    p->next = CreateBtreeNode(q);
    return OK;
}

/**
 * 判断列表是否为空
 * @param list 线性表
 * @return
 */
Status BTree_IfEmpty(BLinkedList list) {
    if (list == NULL) return ERROR;
    if (list->next == NULL) return TRUE;
    return FALSE;
}

/**
 * 出队
 * @param p 队列结点
 * @param q 树结点
 * @return
 */
Status BTree_DeQueue(BLNode *p, BTree *q) {
    BLNode *aq;
    // 删除位置不合理
    if (p == NULL || p->next == NULL) return ERROR;
    // 修改被删除结点 aq 的指针域
    aq = p->next;
    p->next = aq->next;
    *q = aq->data;
    // 释放结点
    free(aq);
    return OK;
}

/**
 * 用队列遍历输出
 * @param t 树
 * @param list 列表
 * @param newLine 是否为新行
 * @param sum 总数
 */
void Traverse_BTree_Queue(BTree t, BLinkedList list, int newLine, int sum) {
    if (t != NULL) {
        printf(" [ ");
        BTree_EnQueue(list, t->ptr[0]);
        for (int i = 1; i <= t->keyNum; ++i) {
            printf(" %d ", t->key[i]);
            BTree_EnQueue(list, t->ptr[i]);
        }
        sum += t->keyNum + 1;
        printf(" ] ");
        if (newLine == 0) {
            printf("\n");
            newLine = sum - 1;
            sum = 0;
        } else {
            newLine--;
        }
    }
    BTree p = NULL;
    // 判断是否为空
    if (BTree_IfEmpty(list) == FALSE) {
        // 出队以 P 返回
        BTree_DeQueue(list, &p);
        // 遍历出队结点
        Traverse_BTree_Queue(p, list, newLine, sum);
    }
}

/**
 * 销毁队列
 * @param list 列表
 */
void Destroy_BTree_Queue(BLinkedList list) {
    BLinkedList p;
    if (list != NULL) {
        p = list;
        // 逐一释放
        list = list->next;
        free(p);
        Destroy_BTree_Queue(list);
    }
}

/**
 * 打印 B 树
 * @param t B 树
 */
bool Print_BTree(BTree t) {
    BLinkedList list = NULL;
    if (t == NULL) {
        printf("B 树为空树.\n");
        return true;
    }
    Init_BTree_Queue(&list);
    Traverse_BTree_Queue(t, list, 0, 0);
    Destroy_BTree_Queue(list);
    return true;
}

/**
 * 生成新的根节点t, 原 p 和 q 为子树指针
 * @param t 树
 * @param k 关键字
 * @param p 子树指针
 * @param q 子树指针
 */
void BTree_New_Root(BTree *t, BKeyType k, BTNode *p, BTNode *q) {
    // 分配空间
    *t = (BTNode *) malloc(sizeof(BTNode));
    (*t)->keyNum = 1;
    (*t)->ptr[0] = p;
    (*t)->ptr[1] = q;
    (*t)->key[1] = k;
    // 调整结点 p 和 q 的双亲指针
    if (p != NULL) p->parent = *t;
    if (q != NULL) q->parent = *t;
    (*t)->parent = NULL;
}

/**
 * 关键字k 和结点q 分别插入到p->key[i+1]和p->ptr[i+1]中
 * @param p 结点
 * @param i 索引位置
 * @param k 关键字
 * @param q 结点
 */
void Insert_BTNode(BTNode *p, int i, BKeyType k, BTNode *q) {
    // 整体后移后空出一个位置
    for (int j = p->keyNum; j > i; j--) {
        p->key[j + 1] = p->key[j];
        p->ptr[j + 1] = p->ptr[j];
    }
    p->key[i + 1] = k;
    p->ptr[i + 1] = q;
    if (q != NULL) q->parent = p;
    p->keyNum++;
}

/**
 * 将结点 p 分裂成两个结点, 前一半保留, 后一半移入结点 q
 * @param p 待分裂的结点
 * @param q 待移入结点
 */
void Split_BTNode(BTNode *p, BTNode **q) {
    // 中间值
    int s = (bOrder + 1) / 2;
    // 分配内存空间
    *q = (BTNode *) malloc(sizeof(BTNode));
    // 后一半移入结点 q
    (*q)->ptr[0] = p->ptr[s];
    for (int i = s + 1; i <= bOrder; ++i) {
        (*q)->key[i - s] = p->key[i];
        (*q)->ptr[i - s] = p->ptr[i];
    }
    (*q)->keyNum = p->keyNum - s;
    (*q)->parent = p->parent;
    // 修改双亲指针
    for (int i = 0; i <= p->keyNum - s; ++i) {
        if ((*q)->ptr[i] != NULL) {
            (*q)->ptr[i]->parent = *q;
        }
    }
    // 结点 p 的前一半保留
    p->keyNum = s - 1;
}

/**
 * 在树 t 中插入关键字 k, 返回插入结果
 * @param t 树
 * @param i 索引位置
 * @param k 关键字
 * @param p 结点
 */
void Insert_BTree(BTree *t, int i, BKeyType k, BTNode *p) {
    // t 是空树
    if (p == NULL) {
        // 仅生成函关键字 k 的根节点
        BTree_New_Root(t, k, NULL, NULL);
    } else {
        BKeyType x = k;
        BTNode *q = NULL;
        // 设定需要新节点标志和插入完成标志
        int finishTag = 0, newRootTag = 0, s;
        while (finishTag == 0 && newRootTag == 0) {
            // 将关键字x 和结点q 分别插入到p->key[i+1]和 p->ptr[i+1]
            Insert_BTNode(p, i, x, q);
            if (p->keyNum <= bMax) {
                // 插入完成
                finishTag = 1;
            } else {
                // 计算中间值
                s = (bOrder + 1) / 2;
                // 分裂结点
                Split_BTNode(p, &q);
                x = p->key[s];
                // 查找 x 插入的位置
                if (p->parent) {
                    p = p->parent;
                    i = Search_BTNode(p, x);
                } else {
                    // 没找到 x, 需要新结点
                    newRootTag = 1;
                }
            }
        }
        // 根结点已分裂为结点 p 和 q
        if (newRootTag == 1) {
            // 生成根节点 t, p和q为子树指针
            BTree_New_Root(t, x, p, q);
        }
    }
}

/**
 * 寻找替代值(右子树中最小的关键字)
 * 查找树结点
 * @param t 树
 * @param k 关键字
 * @param i 索引
 */
int Find_BTNode(BTNode *p, BKeyType k, int *i) {
    // 结点p中查找关键字失败
    if (k < p->key[1]) {
        *i = 0;
        return 0;
    } else {
        // 在结点p中查找
        *i = p->keyNum;
        while (k < p->key[*i] && *i > 1) {
            i--;
        }
        if (k == p->key[*i]) {
            return 1;
        }
        return 0;
    }
}

/**
 * 寻找相邻关键字(右子树中最小的关键字)
 * @param p 结点
 * @param i 索引
 */
void Substitution(BTNode *p, int i) {
    BTNode *q;
    for (q = p->ptr[i]; q->ptr[0] != NULL; q = q->ptr[0]);
    // 复制关键字
    p->key[i] = q->key[1];
}

/**
 * 从p节点删除key[i]和它的孩子指针ptr[i]
 * @param p 结点p
 * @param i 索引
 */
void Remove_BTNode(BTNode *p, int i) {
    for (int j = i + 1; j <= p->keyNum; ++j) {
        p->key[j - 1] = p->key[i];
        p->ptr[j - 1] = p->ptr[j];
    }
    p->keyNum--;
}

/**
 * 双亲结点p, 右结点q合并入左结点aq
 * @param p
 * @param i
 */
void Combine_Btree(BTNode *p, int i) {
    BTNode *q = p->ptr[i];
    BTNode *aq = p->ptr[i - 1];
    // 将双亲结点的关键字p.key[i]插入到左节点aq
    aq->keyNum++;
    aq->key[aq->keyNum] = p->key[i];
    aq->ptr[aq->keyNum] = q->ptr[0];
    // 将右结点q中的所有关键字插入到左结点aq中
    for (int j = 1; j <= q->keyNum; ++j) {
        aq->keyNum++;
        aq->key[aq->keyNum] = q->key[j];
        aq->ptr[aq->keyNum] = q->ptr[j];
    }
    // 将双亲结点p的p.key[i]后的关键字向前移动1位
    for (int j = i; j < p->keyNum; ++j) {
        p->key[j] = p->key[j + 1];
        p->ptr[j] = p->ptr[j + 1];
    }
    // 修改双亲结点p的keyNum值
    p->keyNum--;
    // 释放右结点q的空间
    free(q);
}

/**
 * 将双亲结点p中的第一个关键字移入左结点aq中, 将右结点q中的第一个关键字移入到双亲结点p中
 * @param p
 * @param i
 */
void Move_Left_Btree(BTNode *p, int i) {
    BTNode *aq = p->ptr[i - 1];
    BTNode *q = p->ptr[i];
    // 把双亲结点p中的关键字移动到左兄弟aq中
    aq->keyNum++;
    aq->key[aq->keyNum] = p->key[i];
    aq->ptr[aq->keyNum] = p->ptr[i]->ptr[0];
    // 把右兄弟q中关键字移动到双亲结点p中
    p->key[i] = q->key[1];
    q->ptr[0] = q->ptr[1];
    q->keyNum--;
    // 将右兄弟q中所有关键字向前移动1位
    for (int j = i; j <= aq->keyNum; ++j) {
        aq->key[j] = aq->key[j + 1];
        aq->ptr[j] = aq->ptr[j + 1];
    }
}

/**
 * 将双亲结点p中的最后一个关键字移入右结点q中, 将左结点aq中的最后一个关键字移入到双亲结点p中
 * @param p
 * @param i
 */
void Move_Right_Btree(BTNode *p, int i) {
    BTNode *q = p->ptr[i];
    BTNode *aq = p->ptr[i - 1];
    // 将右兄弟q中的所有关键字向后移动一位
    for (int j = q->keyNum; j > 0; --j) {
        q->key[j + 1] = q->key[j];
        q->ptr[j + 1] = q->ptr[j];
    }
    // 将双亲结点p移动关键字到右兄弟q中
    q->ptr[1] = q->ptr[0];
    q->key[1] = p->key[i];
    q->keyNum++;
    // 将左兄弟aq中最后一个结点关键字移动到双亲结点p中
    p->key[i] = aq->key[aq->keyNum];
    p->ptr[i]->ptr[0] = aq->ptr[aq->keyNum];
    aq->keyNum--;
}

/**
 * 调整B树
 * @param p 结点
 * @param i 索引
 */
void Adjust_BTree(BTNode *p, int i) {
    if (i == 0) {
        // 删除最左边的关键字
        if (p->ptr[1]->keyNum > bMin) {
            // 右结点可以借
            Move_Left_Btree(p, 1);
        } else {
            // 右兄弟不够借
            Combine_Btree(p, 1);
        }
    } else if (i == p->keyNum) {
        // 删除最右边的关键字
        if (p->ptr[i - 1]->keyNum > bMin) {
            // 左节点可以借
            Move_Right_Btree(p, 1);
        } else {
            // 左结点不够借
            Combine_Btree(p, i);
        }
    } else if (p->ptr[i - 1]->keyNum > bMin) {
        // 删除的关键字在中部且左结点够借
        Move_Right_Btree(p, 1);
    } else if (p->ptr[i + 1]->keyNum > bMin) {
        // 删除的关键字在中部且右结点够借
        Move_Left_Btree(p, 1);
    } else {
        // 删除的关键字在中部且左右结点都不够借
        Combine_Btree(p, 1);
    }
}

/**
 * 删除树结点
 * @param t 树
 * @param k 关键字
 */
int Delete_BTNode(BTNode *p, BKeyType k) {
    if (p == NULL) return 0;
    else {
        // 查找结点所在位置
        int i = 0;
        //  查找结点
        int foundTag = Find_BTNode(p, k, &i);
        // 查找成功
        if (foundTag == 1) {
            // 删除非叶子结点
            if (p->ptr[i - 1] != NULL) {
                // 寻找相邻关键字(右子树中最小的关键字)
                Substitution(p, i);
                // 执行删除操作
                Delete_BTNode(p->ptr[i], p->key[i]);
            } else {
                // 从叶子结点p中位置查找并删除关键字k
                Remove_BTNode(p, i);
            }
        } else {
            // 沿孩子结点递归查找并删除关键字
            foundTag = Delete_BTNode(p->ptr[i], k);
        }
        if (p->ptr[i] != NULL) {
            // 删除后关键字个数小于min
            if (p->ptr[i]->keyNum < bMin) {
                // 调整B树
                Adjust_BTree(p, i);
            }
        }
        return foundTag;
    }
}

/**
 * 删除树 t 中的关键字
 * @param t 树
 * @param k 关键字
 */
void Delete_BTree(BTree t, BKeyType k) {
    BTNode *p;
    int a = Delete_BTNode(t, k);
    if (a == 0) {
        // 关键字不在树中
        printf("   关键字%d不在B树中\n", k);
    } else if (t->keyNum == 0) {
        // 调整
        p = t;
        t = t->ptr[0];
        free(p);
    }
}

/**
 * 销毁B树
 * @param t B树
 */
void Destroy_BTree(BTree *t) {
    BTNode *p = *t;
    if (p != NULL) {
        for (int i = 0; i < p->keyNum; ++i) {
            Destroy_BTree(&p->ptr[i]);
        }
        free(p);
    }
    *t = NULL;
}
















